#include <stdio.h>
#include <stdlib.h>

struct data{
    int val;
    struct data *next;
};

int thirdMax(int* nums, int numsSize){
    if(numsSize == 0){
        return 0;
    }

    int count = 0;
    struct data*max_num = NULL, *mid_num = NULL, *min_num = NULL;
    for(int i = 0; i < numsSize; i++){
        if(count == 3){
            if(nums[i] == min_num->val || nums[i] == mid_num->val || nums[i] == max_num->val){
                continue;
            }

            if(nums[i] > max_num->val){
                min_num->val = mid_num->val;
                mid_num->val = max_num->val;
                max_num->val = nums[i];
            }else if(nums[i] > mid_num->val){
                min_num->val = mid_num->val;
                mid_num->val = nums[i];
            }else if(nums[i] > min_num->val){
                min_num->val = nums[i];
            }

            //printf("max:%d\t mid:%d\tmin:%d", max_num->val, mid_num->val, min_num->val);

            continue;
        }

        if(count == 2){
            if(nums[i] == mid_num->val || nums[i] == max_num->val){
                continue;
            }

            struct data*tmp = (struct data*)malloc(sizeof(struct data));
            tmp->val = nums[i];
            tmp->next = NULL;
            if(nums[i] > max_num->val){
                min_num = mid_num;
                mid_num = max_num;
                max_num = tmp;
            }else if(nums[i] > mid_num->val){
                min_num = mid_num;
                mid_num = tmp;
                min_num->next = mid_num;
                mid_num->next = max_num;
            }else{
                min_num = tmp;
                min_num->next = mid_num;
            }
            //printf("max:%d\t mid:%d\tmin:%d", max_num->val, mid_num->val, min_num->val); 

            count = 3;
            continue;
        }

        if(count == 1){
            if(nums[i] == max_num->val){
                continue;
            }

            struct data*tmp = (struct data*)malloc(sizeof(struct data));
            tmp->val = nums[i];
            tmp->next = NULL;
            if(nums[i] > max_num->val){
                max_num->next = tmp;
                mid_num = max_num;
                max_num = tmp;
            }else{
                mid_num = tmp;
                mid_num->next = max_num;
            }

            //printf("max:%d\t mid:%d\t", max_num->val, mid_num->val);
            count = 2;
            continue;
        }

        if(count == 0){
            max_num = (struct data*)malloc(sizeof(struct data));
            max_num->val = nums[i];
            max_num->next = NULL;
            //printf("max:%d\t", max_num->val);
            count = 1;
            continue;
        }

    }

    if(count != 3){
        return max_num->val;
    }else{
        return min_num->val;
    }
}